package com.kangkang.leetcode20;

public class Test2908 {
    public static void main(String[] args) {
        int[] a = {5,4,8,7,10,2};
        int i = new Solution1().minimumSum(a);
        System.out.println(i);
    }
}

class Solution2908 {
    public int minimumSum(int[] nums) {
        if (nums.length < 3) {
            return -1;
        }
        int status = 0;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = nums.length-1; j-i > 1; j--) {
                int min = Integer.MAX_VALUE;
                for (int k = i+1; k <= j-1; k++) {
                    if(nums[k]>Math.max(nums[i],nums[j]))
                    min=Math.min(min,nums[k]);
                }
                if(min!=Integer.MAX_VALUE){
                    result = Math.min(result,nums[i]+nums[j]+min);
                    status=1;
                }
            }
        }
        return status==0?-1:result;
    }
}
class Solution1 {
    public int minimumSum(int[] nums) {
        int[] left = new int[nums.length];
        left[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            left[i] = Math.min(nums[i],left[i-1]);
        }
        int right = nums[nums.length-1];//当前数右面最小数
        int result = Integer.MAX_VALUE;
        for(int i = nums.length - 2; i > 0 ; i--) {
            if(nums[i]>left[i]&&nums[i]>right){
                result = Math.min(result,left[i]+right+nums[i]);
            }
            right = Math.min(right,nums[i]);
        }
        return result==Integer.MAX_VALUE?-1:result;
    }
}